package code.starivan.niuke.jianoffer;


/**
 * Created by Ivan on 2015/8/23.
 */
public class eConTree {

    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || pre.length == 0 || in == null || in.length == 0)
            return null;
        if(in.length!=pre.length){
            return null;
        }

        return geneTree(pre, 0, in, 0, in.length);
    }

    private TreeNode geneTree(int[] pre, int startIndex1,
                              int[] in, int startIndex2, int length) {
        if (length <= 0) {
            return null;
        } else if (length == 1) {
            return new TreeNode(pre[startIndex1]);
        }
       else{
            int val = pre[startIndex1];
            TreeNode node = new TreeNode(val);
            int leftLength=0;
            while (leftLength<length){
                if(in[leftLength+startIndex2]==val) {
                    break;
                }else{
                    leftLength++;
                }
            }

            int rightLength=length-1-leftLength;
            if(leftLength>0){
                node.left=geneTree(pre, startIndex1 + 1,  in, startIndex2,leftLength);
            }else {
                node.left=null;
            }

            if(rightLength>0){
                node.right=geneTree(pre, startIndex1 + leftLength+1,  in, startIndex2+leftLength+1,rightLength);
            }else{
                node.right=null;
            }

            return node;
        }
    }
}
